//题目描述
//​约翰打算建一个围栏来圈养他的奶牛。作为最挑剔的兽类，奶牛们要求这个围栏必须是正方形的，而且围栏里至少要有 C(1≤C≤500)个草场，来供应她们的午餐。
//约翰的土地上共有 N(C≤N≤500)个草场，每个草场在一块1x1的方格内，而且这个方格的 坐标不会超过 10000。
//有时候，会有多个草场在同一个方格内，那他们的坐标就会相同。现求围栏的最小边长为多少。


#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;


const int N = 505;

struct Point {
	int x, y;
}arr[N];
int tmp[N];

bool cmp(const Point& a, const Point& b) //从小到大排序
{
	if (a.x != b.x) return a.x < b.x;
	else return a.y < b.y;
}

bool check_y(Point* arr, int n, int C, int b, int e, int l) { //第四个位置传起始点坐标，第五个位置传终止点坐标,第六位传正方形边长l
	int cnt = 0;
	for (int i = b; i <= e; i++) {
		tmp[cnt++] = arr[i].y; //计算在给定点范围中有多少个点
	}
	sort(tmp, tmp + cnt);
	for (int i = C - 1; i < cnt; i++) {
		if (tmp[i] - tmp[i - C + 1] < l) return true;
	}
	return false;
	
}

bool check(Point* arr, int n, int C, int l) {
	int j = 0; //用边长 L 圈出来
	for (int i = 0; i < n; i++) {
		while (arr[i].x - arr[j].x >= l)  j += 1;
		if (i - j + 1 < C)  continue; //x坐标线的扫描
		if (check_y(arr, n, C, j, i, l)) return true;
	}
	return false;
}


int bs(int l, int r, Point* arr, int n, int C) {
	int mid = 0;
	while (l < r)
	{
		mid = (l + r) >> 1;
		if (check(arr, n, C, mid)) r = mid; //从后面过来
		else l = mid + 1;
	}
	return l; //找到合适的边长值
}


int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int C, n;
	
	cin >> C >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i].x >> arr[i].y;
	}
	sort(arr, arr + n, cmp);

	cout << bs(0, 10000, arr, n, C) << endl;

	return 0;
}